package com.cty.A_GeneralDataStructures.C_Tree.Tree234;

import com.cty.F_common.DataItem;

/**
 * @Auther: cty
 * @Date: 2020/6/16 19:33
 * @Description: 234 Tree
 * 应用场景：
 *      当数据量大时，考虑哈希表或树
 *          当数据量不可预测时，考虑树
 *              当数据是不是随机输入时，考虑234树（平衡树）
 * 重要操作：
 *      ① find(long): DataItem    O(logN)
 *      ② insert(DataItem): void    O(logN)
 *      ③ delete(long): DataItem    O(logN)
 *      ④ displayTree234(): void    O(N)
 * @version: 1.0
 */
public class Tree234 {
    private Node root;
    private DataItem nonItem;

    public Tree234(){
        root = new Node();
        nonItem = new DataItem(-1);
    }

    /**
     * 根据关键字获取指定节点合适的子节点
     * @param node
     * @param key
     * @return
     */
    public Node getNextNode(Node node, long key){
        // 假设节点非空、非满且非叶子节点
        int i;
        int num = node.getItemNums();
        for(i=0; i<num; i++)
            if(key < node.getItem(i).getKey())
                break;
        return node.getChild(i);
    }

    /**
     * 查找  O(logN)
     * @param key
     * @return
     */
    public DataItem find(long key){
        Node current = root;
        while(true)
            if(current.findItem(key) != null)
                return current.findItem(key);
            else if(current.isLeaf())
                return null;
            else
                current = getNextNode(current, key);
    }

    /**
     * 插入
     * @param item
     */
    public void insert(DataItem item){
        Node current = root;
        while(true)
            if(current.isFull()){
                split(current);
                current = current.getParent();
                current = getNextNode(current, item.getKey());
            }else if(current.isLeaf()) {
                current.insertItem(item);  // 在非满叶子节点处插入
                return;
            }else
                current = getNextNode(current, item.getKey());  // 有子节点，继续向下查找
    }  // end insert()

    /**
     * 节点分裂
     * @param node
     */
    public void split(Node node){
        Node parent;
        Node right = new Node();
        Node child2 = node.getChild(2);
        Node child3 = node.getChild(3);
        DataItem itemC = node.removeItem();
        DataItem itemB = node.removeItem();

        // 获取父节点
        if(node == root){  // 顶点分裂是234树层数增加的唯一途径
            root = new Node();
            parent = root;
            root.connectChild(0, node);
        }else
            parent = node.getParent();

        // 将数据项放入节点
        int index = parent.insertItem(itemB);
        right.insertItem(itemC);

        // 将两个子节点连接到右兄弟节点
        right.connectChild(0, child2);
        right.connectChild(1, child3);

        // 父节点高位子节点上移，留出空位连接右兄弟节点
        for(int i=parent.getItemNums()-1; i>index; i--){
            Node temp = parent.disConnectChild(i);
            parent.connectChild(i+1, temp);
        }
        parent.connectChild(index+1, right);
    }  // end split()

    /**
     * 删除（标记节点，并非实际删除）  O(logN)
     * @param key
     * @return
     */
    public DataItem delete(long key){
        // 查找
        Node current = root;
        while(true){
            DataItem find = current.findItem(key);
            if(find != null){
                DataItem temp = new DataItem(find.getKey());
                temp.setData(find.getData());

                find.setKey(-1);
                return temp;
            }else if(current.isLeaf())
                return null;
            else
                current = getNextNode(current, key);
        }
    }  // end delete()

    /**
     * 遍历234树
     */
    public void displayTree234(){
        recDisplayTree(root, 0, 0);
    }

    /**
     * 递归显示234树
     * @param node
     * @param level
     * @param childNum
     */
    public void recDisplayTree(Node node, int level, int childNum){
        // 显示当前节点
        System.out.print("level=" + level + " child=" + childNum + " ");
        node.displayItem();

        // 递归显示所有子节点
        for(int i=0; i<=node.getItemNums(); i++){
            if(node.getChild(i) != null)
                recDisplayTree(node.getChild(i), level+1, i);
            else
                break;
        }
    }

}  // end Tree234
